package TOP101;

/**
 * @Question BM20
 * @Date 2022/11/8 21:30
 * @Solution
 */
public class BM20 {
    int kmod=1000000007;
    int count=0;
    public int InversePairs(int [] array) {
        mergeSort(array,0,array.length-1);
        return count%kmod;
    }
    public void mergeSort(int[] array,int left,int right) {
        //分割
        int mid=(left+right)/2;
        if(left<right) {
           mergeSort(array,left,mid);
           mergeSort(array,mid+1,right);
           merge(array,left,mid,right);
        }
    }
    public void merge(int[] array,int left,int mid,int right) {
        int[] arr=new int[right-left+1];
        int dex=0;//临时数组下标
        int l=left;
        int c=mid+1;
        while(l<=mid && c<=right) {
            if(array[l]<array[c]) {
                arr[dex++]=array[l];
                l++;
            } else {
                count++;
                arr[dex++]=array[c];
                c++;
            }
        }
        while(l<=mid) {
            arr[dex++]=array[l];
            l++;
        }
        while(c<=right) {
            arr[dex++]=array[c];
            c++;
        }
        for(int i:arr) {
            array[left++]=i;
        }
    }
}
